package woa.stack;

/**
 * 最小栈
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * push(x) —— 将元素 x 推入栈中。
 * pop() —— 删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 *
 * 输入：
 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
 * [[],[-2],[0],[-3],[],[],[],[]]
 *
 * 输出：
 * [null,null,null,null,-3,null,0,-2]
 *
 * 解释：
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.getMin();   --> 返回 -2.
 *
 * @author wangpeng
 * @date 2021/11/28
 */
public class MinStack {

    Node head, tail;

    public MinStack() {

    }

    public class Node {

        public int val;
        public int min;
        public Node next;
        public Node prev;

        public Node() {}

        public Node(int val) {
            this.val = val;
            min = val;
        }
    }

    public void push(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = tail.next;
            if (val > newNode.prev.min) {
                newNode.min = newNode.prev.min;
            }
        }
    }

    public void pop() {
        Node node = tail;
        if (head == node) {
            head = node.prev;
        }
        tail = node.prev;
        if (tail != null) {
            tail.next = null;
        }
    }

    public int top() {
        return tail.val;
    }

    public int getMin() {
        return tail.min;
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(2);
        minStack.push(2);
        minStack.push(2);
        minStack.top();
        minStack.pop();
        minStack.getMin();
        minStack.pop();
        minStack.getMin();
        minStack.pop();
        minStack.push(2);
        minStack.top();
        minStack.getMin();
        minStack.push(2);
        minStack.top();
        minStack.getMin();
        minStack.pop();
        minStack.getMin();
    }
}
